package game;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Anirban Laha IISc
 * 
 * Analyzes the strategic form game from the payoff matrix generated.
 * and draws conclusion regarding the presence of strongly dominant strategy
 * equilibrium, weakly dominant strategy equilibrium and pure strategy Nash
 * Equilibrium.
 */

public class GameAnalyzer {
    
    private StrategicGame game;
    
    private List<Integer>[] indexOrderList;
    
    private int[] stronglyDominantStrategyList;
    
    private int[] weaklyDominantStrategyList;
    
    /**
     * 
     * @param inputGame
     * @param list
     * 
     * Constructor for GameAnalyzer which takes in the input strategic form game 
     * generated by PayoffMatrixGenerator and the order of rearrangement of the
     * utilities of each player
     * 
     * This initializes all the objects which store information about the equilibria
     * of the game
     */
    private GameAnalyzer(final StrategicGame inputGame, final List<Integer>[] list) {
        game = inputGame;
        indexOrderList = list;
        stronglyDominantStrategyList = new int[game.getNumPlayers()];
        weaklyDominantStrategyList = new int[game.getNumPlayers()];
        for(int i=0; i<game.getNumPlayers(); i++) {
            stronglyDominantStrategyList[i] = -1;
            weaklyDominantStrategyList[i] = -1;
        }
    }
    
    /**
     * Main method analyzing the game
     * It finds out the list of dominant strategies (both strong and weak) for every player
     * and also the probable Nash equilibrium points according to the best responses of each
     * player for a particular combination of strategies of other players
     * 
     * Finally it outputs the Dominant Strategy equilibria and the pure strategy equilibria
     * from the information obtained in the above paragraph.
     *
     * The flags strongFlag and weakFlag help to find out if all the players have 
     * corresponding dominant strategies. Only then can we say that there exists 
     * a dominant strategy equilibrium
     * 
     * utilList contains the utilities for player i in the rearranged format
     * 
     * probableNEPoint stores the probable PSNE strategy profile according to the best responses 
     * of each player for a particular combination of strategies of other players
     */
    private void analyze() {
        boolean weakFlag = true, strongFlag = true;
        @SuppressWarnings("unchecked")
        List<Integer>[] probableNEPoint = new List[game.getNumPlayers()];
        for(int i=0; i < game.getNumPlayers(); i++) {
            List<Double> utilList = game.getPayoffMatrix()[i];
            int numActions = game.getActions()[i];
            
            strongFlag = findStronglyDominantStrategy(utilList, numActions, i) && strongFlag ;
            weakFlag = findWeaklyDominantStrategy(utilList, numActions, i) &&  weakFlag;
            probableNEPoint[i] = findBestResponses(utilList, numActions, i);
        }
        findDominantEquilibria(weakFlag, strongFlag);
        findNashEquilibria(probableNEPoint);
    }
    

    /**
     * 
     * @param utilList
     * @param numActions
     * @param player
     * @return
     * 
     * listIndexOrder: Contains the codes/indices for the order of rearrangement of utilities of player
     *      so that the contiguous property is maintained for different strategies for a player for a
     *      particular combination of strategies of other players
     *      
     * codes: Contains code for the probable PSNE point according to best response correspondence
     * 
     * bestResponse: The best responses of player for a particular combination of other player strategies.
     */
    private List<Integer> findBestResponses(List<Double> utilList,
            int numActions, int player) {
        List<Integer> listIndexOrder = indexOrderList[player];
        List<Integer> codes = new ArrayList<Integer>();
        for(int j=0; j < utilList.size(); j+=numActions) {
            List<Integer> bestResponse = findWeakGreatestIndex(utilList, j, numActions);
            for(Integer num : bestResponse) {
                codes.add(listIndexOrder.get(num.intValue() + j));
            }
        }
        return codes;
    }

    /**
     * 
     * @param probableNEPoint
     * 
     * Finds the intersection among the list of probable PSNE points of different players
     * and outputs the points in the intersection. The points are present in the form of
     * codes. These need to be decoded to get the actual indices of the strategy profile.
     */
    private void findNashEquilibria(List<Integer>[] probableNEPoint) {
        List<Integer> result = probableNEPoint[0];
        for(int i=1; i < game.getNumPlayers(); i++) {
            result = listIntersection(result, probableNEPoint[i]);
        }
        for(Integer indexCode : result) {
            int[] indices = decodeIndex(indexCode);
            System.out.println("\nPure Strategy Nash Equilibrium : " + Arrays.toString(indices));
        }
        if(result.isEmpty()) {
            System.out.println("\nPure Strategy Nash Equilibrium does not exist!!");
        }
    }
    
    /**
     * 
     * @param actions
     * @return the code of a strategy profile when the inputs are the indices of the strategies.
     */
    @SuppressWarnings("unused")
    private int encodeIndex(int[] actions) {
        int positionValue = 1;
        int code = 0;
        int players = game.getNumPlayers();
        for(int i=0; i < players; i++) {
            code += positionValue * actions[i];
            positionValue *= game.getActions()[i];
        }
        return code;
    }
    
    /**
     * 
     * @param code
     * @return the indices of the strategies corresponding to the code of a strategy profile
     */
    private int[] decodeIndex(int code) {
        int players = game.getNumPlayers();
        int[] indices = new int[players];
        for(int i = 0 ; i< players; i++) {
            int action = game.getActions()[i];
            indices[i] = code % action;
            code /= action;
        }
        return indices;
    }

    /**
     * 
     * @param weakFlag
     * @param strongFlag
     * 
     * Outputs the Strongly and Weakly dominant strategy equilibria information
     */
    private void findDominantEquilibria(boolean weakFlag, boolean strongFlag) {
        if(strongFlag) {
            System.out.println("\nStrongly Dominant Strategy Equilibrium : " + Arrays.toString(stronglyDominantStrategyList));
        } else {
            System.out.println("\nStrongly Dominant Strategy Equilibrium does not exist!!");
        }
        if(weakFlag) {
            System.out.println("\nWeakly Dominant Strategy Equilibrium : " + Arrays.toString(weaklyDominantStrategyList));
        } else {
            System.out.println("\nWeakly Dominant Strategy Equilibrium does not exist!!");
        }
    }

    /**
     * 
     * @param utilList
     * @param numActions
     * @param player
     * @return
     * 
     * maxAction:   the indices of the strategy for which the utilities are maximum.
     *      If any of those strategies is dominant then we store it in weaklyDominantStrategyList
     *      and return true otherwise false.
     *      
     * j-loop: Iterates through the rearranged utility list of player and finds the 
     *      indices within a block of size numActions for which utilities maximum. 
     *      At every step we store the intersection of the indices obtained with the indices
     *      in maxAction. We deal in blocks as the utilities
     *      for different strategies of a player for a particular combinations for other
     *      players' strategies are arranged in contiguous locations. If the maxAction is
     *      empty finally, we return false, otherwise true.
     *      
     * weaklyDominantStrategyList: Array containing the weakly dominant strategies per player.
     */
    private boolean findWeaklyDominantStrategy(List<Double> utilList,
            int numActions, int player) {
        List<Integer> maxAction = findWeakGreatestIndex(utilList, 0, numActions);
        int j;
        for(j=numActions; j<utilList.size(); j+=numActions) {
            List<Integer> index = listIntersection(findWeakGreatestIndex(utilList, j, numActions), maxAction);
            if(index.isEmpty() ) {
                break;
            }
            maxAction = index;
        }
        if(j == utilList.size()) {
            weaklyDominantStrategyList[player] = maxAction.get(0);
            System.out.println("Weakly Dominant Strategy for Player " + player + ": " + maxAction.get(0));
            return true;
        }
        return false;
    }

    /**
     * 
     * @param weakGreatestIndex
     * @param maxAction
     * @return the list containing the intersection of the elements of the two input lists
     */
    private List<Integer> listIntersection(List<Integer> weakGreatestIndex,
            List<Integer> maxAction) {
        List<Integer> list = new ArrayList<Integer>();
        for(Integer i: weakGreatestIndex) {
            if(maxAction.contains(i)) {
                list.add(i);
            }
        }
        return list;
    }

    /**
     * 
     * @param utilList
     * @param offset
     * @param numActions
     * @return the list of indices of utilList from offset to offset+numActions-1 which
     *      has maximum utilities. Difference of index and offset is actually stored
     */
    private List<Integer> findWeakGreatestIndex(List<Double> utilList, int offset,
            int numActions) {
        List<Integer> list = new ArrayList<Integer>();
        int index = offset;
        list.add(index - offset);
        for(int i=offset + 1; i < numActions + offset; i++) {
            if(utilList.get(i).doubleValue() > utilList.get(index).doubleValue()) {
                index = i;
                list = new ArrayList<Integer>();
                list.add(i-offset);
            }
            else if(utilList.get(i).doubleValue() == utilList.get(index).doubleValue()) {
                list.add(i-offset);
            }
        }
        return list;
    }

    /**
     * 
     * @param utilList
     * @param numActions
     * @param player
     * @return true if player has a dominant strategy otherwise false
     * 
     * maxAction:   the index of the strategy for which the utility is maximum.
     *      If that strategy is dominant then we store it in stronglyDominantStrategyList
     *      and return true otherwise false.
     *      
     * j-loop: Iterates through the rearranged utility list of player and finds the 
     *      index within a block of size numActions for which utility is maximum. we deal in blocks
     *      as the utilities for different strategies of a player for a particular combinations for other
     *      players' strategies are arranged in contiguous locations. If the index does not exist
     *      or is not consistent with maxAction, we return false, otherwise true.
     *      
     * stronglyDominantStrategyList: Array containing the strongly dominant strategies per player.
     */
    private boolean findStronglyDominantStrategy(List<Double> utilList,
            int numActions, int player) {
        int maxAction = findStrictGreatestIndex(utilList, 0, numActions),j;
        for(j=numActions; j<utilList.size(); j+=numActions) {
            int index = findStrictGreatestIndex(utilList, j, numActions);
            if(index == -1 || index != maxAction ) {
                break;
            }
        }
        if(j == utilList.size()) {
            stronglyDominantStrategyList[player] = maxAction;
            System.out.println("Strongly Dominant Strategy for Player " + player + ": " + maxAction);
            return true;
        }
        return false;
    }

    /**
     * 
     * @param utilList
     * @param offset
     * @param numActions
     * @return the index in utilList between offset to offset + numActions -1 which has strictly 
     *      maximum value. Return -1 if no such maximum exists. Otherwise return difference
     *      from offset
     */
    private int findStrictGreatestIndex(List<Double> utilList, int offset,
            int numActions) {
        int index = offset;
        for(int i=offset + 1; i < numActions + offset; i++) {
            if(utilList.get(i).doubleValue() > utilList.get(index).doubleValue()) {
                index = i;
            }
        }
        for(int i=offset; i < numActions + offset; i++) {
            if(index != i && utilList.get(i).doubleValue() == utilList.get(index).doubleValue()) {
                return -1;
            }
        }
        return index - offset;
    }

    /**
     * @return the game
     */
    public StrategicGame getGame() {
        return game;
    }

    /**
     * @return the stronglyDominantStrategyList
     */
    public int[] getStronglyDominantStrategyList() {
        return stronglyDominantStrategyList;
    }

    /**
     * @return the weaklyDominantStrategyList
     */
    public int[] getWeaklyDominantStrategyList() {
        return weaklyDominantStrategyList;
    }

    public static void main(String[] args) {
        String file = new String(args[0]);
        PayoffMatrixGenerator pgen = new PayoffMatrixGenerator(file);
        GameAnalyzer analyzer = new GameAnalyzer(pgen.generate(), pgen.getIndexOrderList());
        analyzer.analyze();
    }


}
